public class Main {
    public static void main(String[] args) {
        int nums1[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22};
        int nums2[] = {0,6};
        Solution s = new Solution();
        double r = s.findMedianSortedArrays(nums1, nums2);
        System.out.println(r);
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if((nums1.length + nums2.length) % 2 == 0){
            double a = find(nums1, 0, nums2, 0, (nums1.length + nums2.length) / 2);
            double b = find(nums1, 0, nums2, 0, (nums1.length + nums2.length) / 2 + 1);
            return (a + b) / 2;
        } else {
            return find(nums1, 0, nums2, 0, (nums1.length + nums2.length) / 2 + 1);
        }
    }

    public double find(int[] nums1, int start1, int[] nums2, int start2, int k){
        // ensure that nums1 is not bigger than nums2, making sure that k1 + k2 is always equal to k
        if (nums1.length - start1 > nums2.length - start2){
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;

            int temp2 = start1;
            start1 = start2;
            start2 = temp2;
        }

        if (start1 == nums1.length){
            return nums2[start2 + k - 1];
        } else if (start2 == nums2.length){
            return nums1[start1 + k - 1];
        }
        if (k == 1){
            return Math.min(nums1[start1], nums2[start2]);
        }

        int k1 = Math.min(k / 2, nums1.length - start1);
        int k2 = Math.min(k - k1, nums2.length - start2);

        if (nums1[start1 + k1 - 1] > nums2[start2 + k2 - 1]){
            return find(nums1, start1, nums2, start2 + k2, k - k2);
        } else if (nums1[start1 + k1 - 1] < nums2[start2 + k2 - 1]) {
            return find(nums1, start1 + k1, nums2, start2, k - k1);
        } else{ // if (nums1[start1 + k1 - 1] == nums2[start2 + k2 - 1])   make sure k1 + k2 = k
            return nums1[start1 + k1 - 1];
        }
    }
}